/*
*  Hashtable.cpp
*  Parser
*
*  Created by Christoph Ehscheidt on 10.02.08.
*  Copyright 2008 __MyCompanyName__. All rights reserved.
*
*/

#include "Hashtable.h"
#include "Element.h"

template <class type>
void Hashtable<type>::reorganize(int tablesize) {
	this->usedSize = 0;
	this->elements = 0;

	List<type >* newTable = new List<type >[tablesize];
	
	for(int i=0; i < this->size; i++) {
		typename List<type>::Iterator iter = this->table[i].begin();  // WARUM?! (MS Studio kann es!)
		
		while(iter != this->table[i].end()) {
			
			
			//count inserts in empty lists
			if( newTable[ (**iter).getHashcode() % tablesize].isEmpty() ) {
				this->usedSize++;
			}
			
			type* element = *iter;
			newTable[ (**iter).getHashcode() % tablesize].append(element);
			
			// count every insert
			this->elements++;
			
			iter++;
		}
	}
	// free old hashtable space
	delete[] this->table;
	
	// link new table
	this->table = newTable;

	this->size = tablesize;
}

/**
*	Compares two keys and give a boolean back, if equal or not.
*	@param key1 pointer for lexem1
*	@param key2 pointer for lexem2
*	
*	@return bool, true if equal
*/
template <class type>
bool Hashtable<type>::isEqualKey(char* key1, char* key2) {
	while (*key1 && *key2) {
		if (*key1++ != *key2++) {
			return false;
		}
	}

	// Both have to point to the NULL-Byte
	return *key1 == *key2;
}

template <class type>
Hashtable<type>::Hashtable() {
	this->table = new List<type >[10];

	this->min = 25;
	this->max = 75;
	this->size = 10;
	this->usedSize = 0;
	this->elements = 0;
}

template <class type>
Hashtable<type>::Hashtable(double min, double max) {
	assert(min <= 50 && min >= 1);
	assert(max > 50 && max <= 100);

	this->table = new List<type >[10];

	
	this->min = min;
	this->max = max;
	this->size = 10;
	this->usedSize = 0;
	this->elements = 0;
}

template <class type>
Hashtable<type>::~Hashtable() {
	/**
	* The elements have to be deleted here, that they wont be deleted by reorganisation but
	* they will kept alive until hashtable will be cleared
	*/
	for (int i = 0; i < this->size; i++) {
		typename List<type>::Iterator iter = this->table[i].begin();

		while (iter != this->table[i].end()) {
			delete *iter;
			iter++;
		}
	}

	delete[] table;
}

/**
* Calculates a hashcode for a string key 
* @param key	key for hashcode
* @param length	length of key
* 
* @return int hashcode
*/
template <class type>
int Hashtable<type>::getHashcode(char* key, int length) {
	return 16 * (int) key[0] + 8 * (int) key[length - 1] + (int) length;
}	

/**
* Insert a (hashcode,element) tuple into the hashtable.
* @param hashcode	hashcode as string
* @param element	element
*/

template <class type>
void Hashtable<type>::put(int hashcode, type* element)  {
	/* Prevent it by the lookUp method
	if(this->keyExists(key)) {
		throw HashtableException("This key already exists.");
	}
	*/
	
	//count free hashcodes		
	if(this->table[hashcode % this->size ].isEmpty()) {
		this->usedSize++;	
	}
	
	this->table[hashcode  % this->size ].append(element);

	//count overall elements
	this->elements++;
	
	//cout << "filled: " <<  this->filledPercentage() << "\n";
	// check if we have enough free space
	if(this->filledPercentage() > this->max) {
		//make it bigger
		this->reorganize(2*this->size);
	}
}


/**
* Calculates how much the table is filled.
* @return double Percentage
*/
template <class type>
double Hashtable<type>::filledPercentage() {
	return (double)this->elements / (double)this->size * 100.0;
}

/**
* Checks if a key already exists.*
*
* @param key			key as string
* @param lexemLength	length of lexem
*
* @return				bool, true if key exists
*/
template <class type>
bool Hashtable<type>::keyExists(char* key, int lexemLength) {
	List<type >* list = &(this->table[ Hashtable<type>::getHashcode(key, lexemLength) % this->size]);
	cout << Hashtable<type>::getHashcode(key, lexemLength) << endl;
	cout << list->getFirst() << endl;
	
	typename List<type >::Iterator iter = list->begin();  // WARUM?! (MS Studio kann es!)
	
	while(*iter != NULL && iter != list->end()) {

		char* keyOfCurrentElement = (*iter)->getKey();

		if(isEqualKey(key, keyOfCurrentElement)) {
			return true;
		}
		iter++;
	}
	
	return false;
}

/**
* Get the value for a key.
* 
* @param key			key as string.
* @param lexemLength	length of lexem
* 
* @return				type value related to the key
*/

template <class type>
type* Hashtable<type>::get(char* key, int lexemLength) {
	List<Element>* list = &this->table[Hashtable<type>::getHashcode(key, lexemLength) % this->size];
	
	List<Element>::Iterator iter = list->begin();  // WARUM?! (MS Studio kann es!)
	
	while(iter != list->end()) {
		char* keyOfCurrentElemet = (*iter)->getLexem();

		if(isEqualKey(key, keyOfCurrentElemet)) {
			return (*iter);
		}
		iter++;
	}
	
	return NULL;
	
}

template <class type>
int Hashtable<type>::countCollisions() {
	return this->elements - this->usedSize;
}

template <class type>
int Hashtable<type>::getSize() {
	return this->size;
}


/**
* Prints the complete hashtable on cout
*/
template <class type>
void Hashtable<type>::print() {
	for (int i = 0; i < this->size; i++) {
		typename List<type >::Iterator iter = this->table[i].begin();  // WARUM?! (MS Studio kann es!)
		cout << i << ": ";
		while(iter != this->table[i].end()) {
			
			cout << *(*iter) << " -> "; 
			iter++;
		}
		
		cout << "\n";
	}
}

/*
* Sets the maximum limit of the used size
* @param max Value (percent)
*/
template <class type>
void Hashtable<type>::setMax(double max) {
	assert(max > this->min && max <= 100);


	this->max = max;
	
	if(this->filledPercentage() > max) {
		this->reorganize(2*this->size);
		this->setMax(max);
	}
}

template <class type>
double Hashtable<type>::getMax() {
	return this->max;
}

/*
* Sets the minimum limit of the used size
* @param min Value (percent)
*/
template <class type>
void Hashtable<type>::setMin(double min)  {
	assert(min <= this->max && min >= 1);

	this->min = min;
	
	if(this->filledPercentage() < min) {
		this->reorganize(this->size / 2);
		this->setMin(min);
	}
}

template <class type>
List<type>* Hashtable<type>::getTable() {
	return this->table;
}

template class Hashtable<Element>;
